/*file chiron src/experiment/mul.js */
/*preamble

    Copyright (c) 2002-2008 Kris Kowal <http://cixar.com/~kris.kowal>
    MIT License
    
    The license terms are stated in full in <license.rst> and at the end
    of all source files.

*/


include('base.js');
include('test.js');

// Very slow in IE 7 and lower
var mul0 = function (str, num) {
    if (!num) return "";
    var newStr = str;
    while (--num) newStr += str;
    return newStr;
};

// A typical string multiplier function
var mul1 = function (str, num) {
    if (!num) return "";
    var result = [str];
    while (--num) result.push(str);
    return result.join("");
};

/* Shortest version, roughly equivalent to mul1, performance-wise.
The falsy num handling is probably not warranted since the function would
handle value 0 correctly without it, but it's done anyway to keep things
equivalent across the variations. */
var mul2 = function (str, num) {
    return num ? Array(num + 1).join(str) : "";
};

// Testing if the regex engine provides a speed boost.
var mul3 = function () {
    function mul (str, num) {
        return Array(num + 1).join(str);
    };
    return function (str, num) {
        return num ? str.replace(/^/, mul("$'", num - 1)) : "";
    };
}();

/* Handle high num values fast by expanding the string at an exponential
rate. An array is used for ``soFar``, but not for ``str``, because this
combination performs best on average cross-browser. */
var mul4 = function (str, num) {
    if (!num) return "";
    var orig = str,
        soFar = [str],
        added = 1,
        left, i;
    while (added < num) {
        left = num - added;
        str = orig;
        for (i = 2; i < left; i *= 2) {
            str += str;
        }
        soFar.push(str);
        added += (i / 2);
    }
    return soFar.join("");
};

// Regex-based approach with mul4 as the supporting function
var mul5 = function (str, num) {
    return num ? str.replace(/^/, mul4("$'", num - 1)) : "";
}

/* use binary interpolation */
var mul6Standard = function (str, num) {
    var acc = [];
    for (var bit = 1; bit <= num; bit <<= 1) {
        if (bit & num)
            acc.push(str);
        str += str; /* double the string */
    }
    return acc.join('');
};

/* a la http://www.liucougar.net/blog/archives/76 */
var mul6IE = function (str, num) {
    var acc = [];
    var strs = [str];
    for (var bit = 1; bit <= num; bit <<= 1) {
        if (bit & num)
            acc.push.apply(acc, strs);
        strs.push.apply(strs, strs);
    }
    return acc.join('');
};

var mul6 = isIE ? mul6IE : mul6Standard;

var regexCapable = "x".replace(/^/, "$'") == "xx";
var mul7 = regexCapable ? function (str, num) {
    return num ? str.replace(/^/, mul6("$'", num - 1)) : "";
} : mul6;

var orders = seq(300, function (n) {
    return n * 3;
}).to(range(3));

// Using a fast multiplier to generate the starting string for each test
var fastMul = mul6;

var results =
list(['mul4', 'mul5', 'mul6', 'mul7']).
each(function (name) {
    var mul = eval(name);
    assertEq(mul('x', 0), '');
    assertEq(mul('x', 15), 'xxxxxxxxxxxxxxx');
    assertEq(mul('x', 16), 'xxxxxxxxxxxxxxxx');
    assertEq(mul('x', 17), 'xxxxxxxxxxxxxxxxx');
    return orders.
    each(function (a) {
        return orders.
        each(function (b) {
            var s = fastMul('+', a);
            return time(name + ' for ' + a + ' * ' + b, function () {
                mul(s, b);
            });
        });
    });
});

include('browser.js');
console.output(tag('table', {}, results.each(function (row) {
    return tag('tr', {}, row.each(function (cell) {
        return tag('td', {}, cell.each(function (item) {
            return tag('li', {}, [string(item)]);
        }));
    }));
})));


/*license

    Legal
    =======
    
    Chiron is a component of the Tale web-game project.
    
    See <credit.txt> for a complete list of
    contributions and their licenses.  All contributions are provided
    under permissive, non-viral licenses including MIT, BSD, Creative Commons
    Attribution 2.5, Public Domain, or Unrestricted.
    
    
    License
    =======
    
    Copyright (c) 2002-2008 Kris Kowal <http://cixar.com/~kris.kowal>
    MIT License
    
    
    MIT License
    -----------
    
    Permission is hereby granted, free of charge, to any person
    obtaining a copy of this software and associated documentation
    files (the "Software"), to deal in the Software without
    restriction, including without limitation the rights to use,
    copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following
    conditions:
    
    The above copyright notice and this permission notice shall be
    included in all copies or substantial portions of the Software.
    
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
    OTHER DEALINGS IN THE SOFTWARE.

*/

